埃氏筛中将内层循环从j = i*i 开始而不是j = 2*i 的主要原因是（）。

def eratosthenes_sieve_for(n):
    if n < 2:
        return []
    is_composite = [False] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if is_composite[i]:
            continue
        primes.append(i)

        # 用for循环模拟C++的 j = i*i; j <=n; j +=i
        for j in range(i * i, n + 1, i):
            is_composite[j] = True

    return primes

对如下代码实现的欧几里得算法（辗转相除法），调用gcd(48 , 18) 得到的调用序列为（）。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

下面代码用分治求“最大连续子段和”，其时间复杂度为（）。

import sys
def solve(a , l , r):
    if l == r:
        return a [l]
    mid = l + (r - l) // 2
    left = solve(a , l , mid)
    right = solve(a , mid + 1 , r)
    sum_val = 0
    lmax = -sys .maxsize - 1
    for i in range(mid , l - 1 , -1):
        sum_val += a [i]
        lmax = max (lmax , sum_val)
    sum_val = 0
    rmax = -sys .maxsize - 1
    for i in range(mid + 1 , r + 1):
        sum_val += a [i]
        rmax = max (rmax , sum_val)
    return max(left , right , lmax + rmax)

if __name__ == "__main__":
    a1 = [-2 , 1 , -3 , 4 , -1 , 2 , 1 , -5 , 4]
    print(solve(a1 , 0 , len(a1)-1))
    a2 = [-5 , -3 , -1 , -4]
    print(solve(a2 , 0 , len(a2)-1))
    a3 = [10]
    print(solve(a3 , 0 , 0))

下面代码实现了欧拉（线性）筛，横线处应填写（）。

def euler_sieve_for(n):
    if n < 2:
        return []
    is_composite = [False] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)

        for j in range(len(primes)):  # 填空处
            p = primes[j]
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                break
    return primes

下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用int 表示，则横线处应该填写（）。

def big_integer_division():
    s, b = input().split()
    b = int(b)
    a = [int(c) for c in s]

    c = []
    rem = 0
    for i in range(len(a)):
        rem = rem * 10 + a[i]
        q = rem // b
        c.append(q)
        rem = rem % b  # 填空处

    pos = 0
    while pos < len(c) - 1 and c[pos] == 0:
        pos += 1

    for i in range(pos, len(c)):
        print(c[i], end='')
    print()

    print(rem)

if __name__ == "__main__":
    big_integer_division()

题关于Python 实现的单链表、双链表和循环链表，下列说法正确的是（）。

双向循环链表中要在结点p 之前插入新结点s（均非空），以下操作正确的是（）。

游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。

A组：A = {12 , 35 , 67 , 89}，B组：B = {20 , 45 , 55 , 78}，下面是归并合并函数的核心循环，横线处应填入（）。

A = [12, 35, 67, 89]
B = [20, 45, 55, 78]

i = 0
j = 0
result = []

while i < len(A) and j < len(B):
    if A[i] < B[j]:  # 填空处
        result.append(A[i])
        i += 1
    else:
        result.append(B[j])
        j += 1

while i < len(A):
    result.append(A[i])
    i += 1

while j < len(B):
    result.append(B[j])
    j += 1

print("合并后的有序排行榜: ", result)

在升序数组中查找第一个大于等于x 的位置，下面循环中横线应填（）。

def lowerBound(a, x):
    l = 0
    r = len(a)
    while l < r:
        mid = l + (r - l) // 2
        if a[mid] >= x:
            r = mid  # 填空处
        else:
            l = mid + 1
    return l

if __name__ == "__main__":
    a1 = [1, 3, 5, 7, 9]
    x1 = 5
    print(f"数组{a1}中第一个≥{x1}的位置: {lowerBound(a1, x1)}")

给定n 根木头，第i 根长度为a [i]。要切成不少于m 段等长木段，求最大可能长度，则横线上应填写（）。

def check(a, m, x):
    cnt = 0
    for length in a:
        if x == 0:
            return True
        cnt += length
        if cnt >= m:
            return True
    return cnt >= m

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    m = int(input[idx])
    idx += 1

    a = []
    mx = 0
    for _ in range(n):
        num = int(input[idx])
        idx += 1
        a.append(num)
        mx = max(mx, num)

    l = 1
    r = mx
    ans = 0

    while l <= r:
        mid = l + (r - l) // 2
        if check(a, m, mid):
            ans = mid
            _________________
        else:
            _________________

    print(ans)

if __name__ == "__main__":
    main()

关于递归函数调用，下列说法错误的是（）。

下面函数删除单向链表中val == x 的节点，并且使用哑结点统一对头结点和中间节点的删除操作。横线处应填（）。

下面程序的运行结果为（）。

def check(n, a, k, dist):
    cnt = 1
    last = a[0]

    for i in range(1, n):
        if a[i] - last >= dist:
            cnt += 1
            last = a[i]

    return cnt >= k

def solve(n, a, k):
    a.sort()

    l = 0
    r = a[-1] - a[0]

    while l < r:
        mid = (l + r + 1) // 2
        if check(n, a, k, mid):
            l = mid
        else:
            r = mid - 1

    return l

if __name__ == "__main__":
    a = [1, 2, 8, 4, 9]
    n = 5
    k = 3
    result = solve(n, a, k)
    print(result)

下面关于排序算法的描述中，不正确的是( )。

有n位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为pivot 的快速排序，请问此次排序的时间复杂度是（）。

def quicksort(a , l , r):
    if l >= r:
        return
    pivot = a [l]
    i , j = l , r
    while i < j :
        while i < j and a [j] >= pivot :
            j -= 1
        while i < j and a [i] <= pivot :
            i += 1
        if i < j :
            a [i], a [j] = a [j], a [i]
    a [l], a [i] = a [i], a [l]
    quicksort(a , l , i - 1)
    quicksort(a , i + 1 , r)

if __name__ == "__main__":
    scores = [60 , 70 , 80 , 90 , 100]
    print("排序前：", scores)
    quicksort(scores , 0 , len(scores)-1)
    print("排序后：", scores) # 输出：[60 , 70 , 80 , 90 , 100]

def quicksort_with_log(a , l , r , depth=0):
    if l >= r:
        return
    print(f "递归深度{depth}，处理区间[{l },{r }]，数组：{a [l:r+1]}")
    pivot = a [l]
    i , j = l , r
    while i < j :
        while i < j and a [j] >= pivot : j -= 1
        while i < j and a [i] <= pivot : i += 1
        if i < j : a [i], a [j] = a [j], a [i]
    a [l], a [i] = a [i], a [l]
    quicksort_with_log(a , l , i-1 , depth+1)
    quicksort_with_log(a , i+1 , r , depth+1)

scores2 = [60 ,70 ,80 ,90 ,100]
print("\n递归过程：")
quicksort_with_log(scores2 , 0 , 4)

快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。

若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。（）

假设数组a的值域范围是D，以下程序的时间复杂度是O(nlogn+nlogD)。

def check(n , a , k , dist): 
    cnt = 1
    last = a [0]
    for i in range(1 , n):
        if a [i] - last >= dist : 
            cnt += 1
            last = a [i]
    return cnt >= k

def solve(n , a , k): 
    a_sorted = a .copy()
    a_sorted .sort()
    l = 0
    r = a_sorted [-1] - a_sorted [0]
    while l < r:
        mid = (l + r + 1) // 2
        if check(n , a_sorted , k , mid): 
            l = mid
        else:
            r = mid - 1
    return l

if __name__   == "__main__": 
    a = [1 , 2 , 8 , 4 , 9]
    n = 5
    k = 3
    result = solve(n , a , k)
    print(result)

线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过"每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现O(n)的时间复杂度。

唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

在一个数组中，如果两个元素a [i] 和a [j]满足i < j 且a [i] > a [j]，则a [i] 和a [j]是一个逆序对。

下面代码可以正确统计数组a 区间[l ,r] 内的逆序对总数。

cnt = 0
def merge_count(a , l , m , r):
    global cnt
    i = l
    j = m + 1
    while i <= m and j <= r:
        if a [i] <= a [j]: 
            i += 1
        else:
            cnt += (m - i + 1)
            j += 1
if __name__  == "__main__":
    a = [2 , 4 , 1 , 3]
    merge_count(a , 0 , 1 , 3)
    print(f "跨区间逆序对数量：{cnt}")

若数组a 已按升序排列，则下面代码可以正确实现“在a 中查找第一个大于等于x 的元素的位置”。

def lowerBound(a, x):
    l = 0
    r = len(a)
    while l < r:
        mid = (l + r) // 2
        if a[mid] >= x:
            r = mid
        else:
            l = mid + 1
    return l

if __name__ == "__main__":
    a1 = [1, 3, 5, 7, 9]
    x1 = 5
    print(f"数组{a1}中第一个≥{x1}的位置: {lowerBound(a1, x1)}")

    x2 = 6
    print(f"数组{a1}中第一个≥{x2}的位置: {lowerBound(a1, x2)}")

    x3 = 10
    print(f"数组{a1}中第一个≥{x3}的位置: {lowerBound(a1, x3)}")

    x4 = 0
    print(f"数组{a1}中第一个≥{x4}的位置: {lowerBound(a1, x4)}")

任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

有一个存储了 n 个整数的线性表，分别用 Python 列表（数组）和自定义单链表两种方式实现。在已知元素下标（或结点对象引用）的前提下，Python 列表的随机访问操作时间复杂度为O(1)；而在 Python 实现的单链表中，已知某结点对象的引用时，在该结点之后插入一个新结点的操作时间复杂度也为O(1)。

若某算法满足递推式：

找数

时间限制：1.0 s

内存限制：512.0 MB

题目描述

给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B，请你帮忙计算有多少数在数组A与 数组B中均出现。

输入格式

第一行包含两个整数n,m。

第二行包含n个正整数a1,a2,...,an表示数组A。

第二行包含m个正整数b1,b2,...,bn表示数组B。

输出格式

输出一个整数，表示在数组A与 数组B中均出现的数的个数。

输入样例

3 5
4 2 3
3 1 5 4 6

输出样例

2

样例解释

样例 1 中，4、3在数组 与 中均出现。

数据范围

对于40%的数据，保证1≤n,m≤1000。

对于100%的数据，保证1≤n,m≤105，1≤ai,bi≤109。

有限不循环小数

时间限制：1.0 s

内存限制：512.0 MB

题目描述

若1/a可化为一个有限的，不循环的小数，则称a为终止数。

请你求出在L到R中终止数的数量。

输入格式

输入一行，包含两个整数L,R。

输出格式

输出一行，包含一个整数，表示L到R中终止数的数量。

输入样例

2 11

输出样例

5

样例解释

在[2,11]终止数有2、4、5、8、10。

数据范围

保证1≤L≤R≤106。